package E_2024;

import java.util.Arrays;

/*
    给定一个数组X和正整数K，请找出使表达式X[i]-x[i+1]…-X[i+k-1]，结果最接近于数组中位数的下标i，如果有多个满足条件，请返回最大的i。
    其中，数组中位数:长度为N的数组，按照元素的值大小升序排列后，下标为N/2元素的值
补充说明:
    1.数组X的元素均为正整数;
    2.X的长度n取值范围: 2<= n <= 1000;
    3.K大于0且小于数组的大小;
    4. i的取值范围:0<=i < 1000;
    5.题目的排序数组X[N]的中位数是X[N/2].
示例1
    输入:
    [50,50,2,3],2
    输出:
    1
    说明:
    1、中位数为50:[50,50,2,3]升序排序后变成[2,3,50,50]，中位数为下标4/2=2的元素50;
    2、计算结果为1:X[50,50,2,3]根据题目计算X[i]-x[i+1]…-X[i+k-1]得出三个数
    0 (X[0]-X[1]= 50 -50)，
    48(X[1]-X[2]= 50 -2)，
    -1(X[2]-X[3]= 2-3)，
    其中48最接近50，因此返回下标1
 */
public class E_100_36 {
    public static void main(String[] args) {
        System.out.println(ans(new int[]{50, 49, 2, 3}, 2));
        System.out.println(ans(new int[]{50, 49, 2, 3,3}, 3));
    }
    // 使用前缀和处理
    // a = i-1   -  i  - x
    // b = i - x - i+k-1
    // x = i-1   -  i   -  a
    // b = i  - i-1  + i  + a
    // b = 2i  - i-1 + a
    public static int ans(int[] arr, int k){
        int[] temp = new int[arr.length - k + 1];
        temp[0] = arr[0];
        for (int i = 1; i < k; i++) {
            temp[0] -= arr[i];
        }
        int left = 1;
        int right = k;
        while(right < arr.length){
            temp[left] = 2*arr[left] - arr[left-1] + temp[left-1] - arr[right];
            left++;
            right++;
        }
        // 获取中位数
        Arrays.sort(arr);
        int mid = arr[arr.length >> 1];
        int ans = 0;
        int mi = mid;
        // 比较最靠近中位数的下标，
        for (int i = 0; i < temp.length; i++) {
            int abs = Math.abs(mid - temp[i]);
            if (mi >= abs){
                mi = abs;
                ans = i;
            }
        }
        return ans;
    }
}
